The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs typically require matching packets on a subset of fields of the packet header or flow label, with the semantics of a sequential search through the ACL rules.
Access control and quality of service features are typically implemented based on programming contained in one or more ACLs. To implement features in hardware, these multiple ACL lists are typically combined into one list, which can be used for programming and associative memory. Various techniques are known for combining these items, such as Binary Decision Diagram (BDD) and Order Dependent Merge (ODM). For example, if there are two ACLs A (having entries A1 and A2) and B (having entries B1 and B2, then ODM combines these original lists to produce one of two cross-product equivalent ordered lists, each with four entries: A1B1, A1B2, A2B1, and A2B2; or A1B1, A2B1, A1B2, and A2B2. These four entries can then be programmed into an associative memory and an indication of a corresponding action to be taken placed in an adjunct memory. Lookup operations can then be performed on the associative and adjunct memories to identify a corresponding action to use for a particular packet being processed. There are also variants of ODM and BDD which may filter out the entries which are unnecessary as their values will never allow them to be matched. Merged entries which are order independent can be sorted based on common masks, and programmed into the block masks of an associative memory (which typically does not significantly reduce the number of block masks required), or can be programmed in any order in an associative memory where each entry has its own mask field. Nonconsecutive merged entries which remain order dependent must maintain their ordering when programmed into an associative memory, and thus cannot be rearranged to reduce or eliminate redundant masks when entries are masked using block masks. Also, one or more of these techniques may produce an increased number of entries and/or block masks required for programming the resultant entries into an associative memory.
An example of an associative memory using block masks is described in Ross et al., “Block Mask Ternary CAM”, U.S. Pat. No. 6,389,506, issued May 12, 2002, which is hereby incorporated by reference. In a nutshell, a block mask is a mask that is applied to each entry of a block of entries. Such an associative memory typically has numerous blocks and corresponding block masks. FIG. 1A shows one such prior art associative memory 100, having multiple blocks 110, 120, and 130, each with corresponding block masks 111, 121, and 131 for blocks of associative memory entries 112, 122, and 132.
FIG. 1B illustrates a prior art approach for combining masks of two ACLs 150 and 152, having masks as shown with their corresponding required ordering. The result of a first approach for combining these lists is shown in ordering 155, in which entries of ACL-2 152 are concatenated at the end of entries of ACL-1 150 to produce an ordering that requires m masks, where m is the sum of the number of masks required for each of ACLs 150 and 152. The results 156 and 157 of a second approach is similar, but allows the mask at the end of a list to be used by both ACLs 150 and 152 if the last required mask of one ACL is the same mask as first required by the other ACL, then the number of masks required is m minus a small number of overlapping masks. However, this does not significantly reduce the overall number of masks required, which can be a problem as the number of different masks in the required order is directly correlated to the number of ACL entries which can be stored in a block mask associative memory. Thus, an efficient way of allocating these masks is desired.